package skiplist

import (
	"fmt"
	"math"
	"math/rand"
)

const (
	MaxLevel = 16 // 最高层数
)

// 跳表节点结构体
type skipListNode struct {
	// 跳表保存的值
	v interface{}
	// 用于排序的分值
	score int
	// 层高
	level int
	// 每层前进指针
	forwards []*skipListNode
}

// 新建跳表节点
func newSkipListNode(v interface{}, score, level int) *skipListNode {
	return &skipListNode{
		v:        v,
		score:    score,
		level:    level,
		forwards: make([]*skipListNode, level, level),
	}
}

// 跳表结构体
type SkipList struct {
	// 跳表头部节点
	head *skipListNode
	// 跳表当前层数
	level int
	// 跳表长度
	length int
}

// 实例化跳表对象
func NewSkipList() *SkipList {
	// 头节点
	head := newSkipListNode(0, math.MinInt32, MaxLevel)
	return &SkipList{
		head:   head,
		level:  1,
		length: 0,
	}
}

// 获取跳表长度
func (that *SkipList) Length() int {
	return that.length
}

// 获取跳表层级
func (that *SkipList) Level() int {
	return that.level
}

// 将节点插入跳表
func (that *SkipList) Insert(v interface{}, score int) int {
	if v == nil {
		return 1
	}
	// 查找插入位置
	cur := that.head
	// 记录每层路径
	update := [MaxLevel]*skipListNode{}
	i := MaxLevel - 1
	for ; i >= 0; i-- {
		for cur.forwards[i] != nil {
			if cur.forwards[i].v == v {
				return 2
			}
			if cur.forwards[i].score > score {
				update[i] = cur
				break
			}
			cur = cur.forwards[i]
		}
		if cur.forwards[i] == nil {
			update[i] = cur
		}
	}
	// 通过随机算法获取该节点层数
	level := 1
	for i := 1; i < MaxLevel; i++ {
		if rand.Int31()%7 == 1 {
			level++
		}
	}

	// 创建一个新的跳表节点
	newNode := newSkipListNode(v, score, level)

	// 原有节点连接
	for i := 0; i <= level-1; i++ {
		next := update[i].forwards[i]
		update[i].forwards[i] = newNode
		newNode.forwards[i] = next
	}

	// 如果当前节点的层数大于之前跳表的层数
	if level > that.level {
		that.level = level
	}

	// 更新跳表长度
	that.length++

	return 0
}

func (that *SkipList) Find(v interface{}, score int) *skipListNode {
	if v == nil || that.length == 0 {
		return nil
	}

	cur := that.head
	for i := that.level - 1; i >= 0; i-- {
		for cur.forwards[i] != nil {
			if cur.forwards[i].score == score && cur.forwards[i].v == v {
				return cur.forwards[i]
			} else if cur.forwards[i].score > score {
				break
			}
			cur = cur.forwards[i]
		}
	}
	return nil
}

func (that *SkipList) Delete(v interface{}, score int) int {
	if v == nil {
		return 1
	}
	// 查找前驱节点
	cur := that.head
	// 记录前驱路径
	update := [MaxLevel]*skipListNode{}
	for i := that.level - 1; i >= 0; i-- {
		update[i] = that.head
		for cur.forwards[i] != nil {
			if cur.forwards[i].score == score && cur.forwards[i].v == v {
				update[i] = cur
				break
			}
			cur = cur.forwards[i]
		}
	}

	cur = update[0].forwards[0]
	for i := cur.level - 1; i >= 0; i-- {
		if update[i] == that.head && cur.forwards[i] == nil {
			that.level = i
		}

		if update[i].forwards[i] != nil {
			update[i].forwards[i] = update[i].forwards[i].forwards[i]
		}
	}

	that.length--

	return 0
}

func (that *SkipList) String() string {
	return fmt.Sprintf("level:%+v, length:%+v", that.level, that.length)
}
